Pattern search is a simple yet powerful machine vision tool. Given a template pattern and an image, its objective is to find all instances of the patterns in the image. Pattern search involves two steps, a search step and a matching step. The search step places the pattern at all valid locations of the image being searched. The matching step determines the goodness of the match between the pattern and the subset of the image centered at a given image location. A normalized correlation method (Ballard D H and Brown C M, “Computer Vision”, Prentice-Hall Inc. 1982) has been widely used as the pattern matching method in many machine vision applications. The match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variation. However, pattern search based on a normalized correlation method is inherently computationally demanding since it requires operations between two (pattern and image region) two-dimensional regions on all valid image locations. Because of the computational complexity, even with the state-of-the-art computers, it is still difficult to achieve real-time performance. This is especially true when the image size is large. Furthermore, normalized correlation does not work well when the pattern being searched is subject to rotation, size, or aspect ratio variation. The match score could drop significantly even if only a few degrees of rotation or a few percent of size change occurs.
One prior art approach to rotation and scale invariance is to rotate and scale the pattern template and try all possible scale and rotation combinations for all valid image locations. However, this imposes even greater computational demand that cannot be reasonably accomplished using the prior art method. Another prior art approach is the use of a geometric pattern matching method such as PatMax introduced by Cognex (Silver, B, “Geometric Pattern Matching for General-Purpose Inspection in Industrial Machine Vision”, Intelligent Vision '99 Conference—Jun. 28–29, 1999). This approach uses geometric information in place of pixel grid-based correlation. For example, it interprets a square as four line segments and a football as two arcs. It extracts key geometric features within an object image (such as boundary encoding) and measures characteristics such as shape, dimensions, angle, arc segments, and shading. It then searches using spatial relationship correspondence between the key geometric features of the pattern template and finds the matches in the new image. This prior art approach requires high edge contrast and low noise between patterns and background to reliably extract the key geometric features. It fails when edges of a pattern are not well defined. This is the inherent problem when using geometric approach in place of pixel grid based approach.
In many application scenarios, the template pattern is a well-defined regular shape such as the shapes used in alignment or registration marks or fiducials for electronic assembly of printed circuit boards or semiconductor manufacturing. Some examples of typical alignment marks for electronic assembly includes circles, rings, cross, bar, triangles, wedges, or multiple squares. Other examples of regular shaped patterns are alphanumeric characters such as the ones used for identification of semiconductor wafers (SEMI M13-0998E “Specification For Alpha Numeric Marking of Silicon Wafers”). This invention seeks to provide a very fast pattern search method that can accurately locate regular shaped patterns of interest in a fraction of the time used by the prior art approach. It therefore forms the basis for invariant search that matches patterns of interest in instances where they vary in size or orientation, when their appearance is degraded, and even when they are partially hidden from view. It retains the advantages of the pixel grid based approach on low contrast and noisy images yet it achieves real-time performance and the advantage of rotation, or scale, or aspect ratio invariance.
The invention provides significant speed advantage in both search and matching steps.